package com.lh.jianzhioffer.专项练习.链表;

import java.net.SocketTimeoutException;
import java.util.Stack;

/**
 * @author: linghao
 * @since: 2023/3/10
 *
 * 给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。
 * 将这两数相加会返回一个新的链表。
 * 可以假设除了数字 0 之外，这两个数字都不会以零开头
 *
 * 利用栈
 */
public class 链表中的两数相加025 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }

        int carry=0;
        ListNode pre = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry!=0){
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int cur = a+b+carry;
            carry = cur/10;
            cur %= 10;
            ListNode temp = new ListNode(cur);
            temp.next = pre;
            pre = temp;
        }
        return pre;
    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

}
